/*
 * @lc app=leetcode.cn id=720 lang=cpp
 *
 * [720] 词典中最长的单词
 */

// @lc code=start
class Tire
{
    vector<Tire *> children;
    bool isWord;

public:
    Tire() : isWord(false)
    {
        children = vector<Tire *>(26, nullptr);
    }

    void insert(string &s)
    {
        Tire *node = this;
        for (char c : s)
        {
            if (node->children[c - 'a'] == nullptr)
            {
                node->children[c - 'a'] = new Tire();
            }
            node = node->children[c - 'a'];
        }
        node->isWord = true;
    }

    bool search(const string &s)
    {
        Tire *node = this;
        for (char c : s)
        {
            // 没有这个单词或者没有单词的前缀，直接返回false
            if (node->children[c - 'a'] == nullptr || !node->children[c - 'a']->isWord)
            {
                return false;
            }
            node = node->children[c - 'a'];
        }
        return (node != nullptr && node->isWord);
    }
};

class Solution
{
public:
    string longestWord(vector<string> &words)
    {
        Tire *tire = new Tire();
        for (string &word : words)
        {
            tire->insert(word);
        }

        string ans;
        for (const string &word : words)
        {
            if (tire->search(word))
            {
                if (word.size() > ans.size() || (word.size() == ans.size() && word < ans))
                {
                    ans = word;
                }
            }
        }

        return ans;
    }
};
// @lc code=end
